package Exams.FeiBu;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class q4 {
    List<String> res = new ArrayList<>();
    // 花括号展开 会员题1087
    public String[] expand(String s) {
        // 先遍历string s 得到一个List<String> 比如对示例1 得到["ab", "c", "de", "f"]
        List<String> cands = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '{') {
                sb = new StringBuilder();
                int j = i + 1;
                while (j < s.length() && s.charAt(j) != '}') {
                    if (s.charAt(j) != ',') {
                        sb.append(s.charAt(j));
                    }
                    j++;
                } // end-while s[j]='}'
                cands.add(sb.toString());
                i = j;
            } else {
                cands.add(s.charAt(i) + "");
            }
        }

        // 回溯
        dfs("", 0, cands);
        Collections.sort(res); // 按字典顺序返回
        return res.toArray(new String[0]);

    }

    // curr:当前的string
    // idx: 正在枚举candidates的哪个string
    private void dfs(String curr, int idx, List<String> cands) {
        if (idx >= cands.size()) {
            res.add(curr);
            return;
        }

        for (int i = 0; i < cands.get(idx).length(); i++) {
            dfs(curr + cands.get(idx).charAt(i), idx + 1, cands);
        }
    }

}

